

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">

<html>


<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">

<base target="_top">
<style type="text/css">
  

/* default css */

table {
  font-size: 1em;
  line-height: inherit;
  border-collapse: collapse;
}


tr {
  
  text-align: left;
  
}


div, address, ol, ul, li, option, select {
  margin-top: 0px;
  margin-bottom: 0px;
}

p {
  margin: 0px;
}


pre {
  font-family: Courier New;
  white-space: pre-wrap;
  margin:0;
}

body {
  margin: 6px;
  padding: 0px;
  font-family: Verdana, sans-serif;
  font-size: 10pt;
  background-color: #ffffff;
  color: #000;
}


img {
  -moz-force-broken-image-icon: 1;
}

@media screen {
  html.pageview {
    background-color: #f3f3f3 !important;
    overflow-x: hidden;
    overflow-y: scroll;
  }

  

  body {
    min-height: 1100px;
    
    counter-reset: __goog_page__;
  }
  
  * html body {
    height: 1100px;
  }
  /* Prevent repaint errors when scrolling in Safari. This "Star-7" css hack
     targets Safari 3.1, but not WebKit nightlies and presumably Safari 4.
     That's OK because this bug is fixed in WebKit nightlies/Safari 4 :-). */
  html*#wys_frame::before {
    content: '\A0';
    position: fixed;
    overflow: hidden;
    width: 0;
    height: 0;
    top: 0;
    left: 0;
  }
  
  .pageview body {
    border-top: 1px solid #ccc;
    border-left: 1px solid #ccc;
    border-right: 2px solid #bbb;
    border-bottom: 2px solid #bbb;
    width: 648px !important;
    margin: 15px auto 25px;
    padding: 40px 50px;
  }
  /* IE6 */
  * html {
    overflow-y: scroll;
  }
  * html.pageview body {
    overflow-x: auto;
  }
  

  
    
    .writely-callout-data {
      display: none;
    }
    

    .writely-footnote-marker {
      background-image: url('MISSING');
      background-color: transparent;
      background-repeat: no-repeat;
      width: 7px;
      overflow: hidden;
      height: 16px;
      vertical-align: top;

      
      -moz-user-select: none;
    }
    .editor .writely-footnote-marker {
      cursor: move;
    }
    .writely-footnote-marker-highlight {
      background-position: -15px 0;
      -moz-user-select: text;
    }
    .writely-footnote-hide-selection ::-moz-selection, .writely-footnote-hide-selection::-moz-selection {
      background: transparent;
    }
    .writely-footnote-hide-selection ::selection, .writely-footnote-hide-selection::selection {
      background: transparent;
    }
    .writely-footnote-hide-selection {
      cursor: move;
    }

    /* Comments */
    .writely-comment-yellow {
      background-color: #ffffd7;
    }
    .writely-comment-orange {
      background-color: #ffe3c0;
    }
    .writely-comment-pink {
      background-color: #ffd7ff;
    }
    .writely-comment-green {
      background-color: #d7ffd7;
    }
    .writely-comment-blue {
      background-color: #d7ffff;
    }
    .writely-comment-purple {
      background-color: #eed7ff;
    }

  


  
  .br_fix span+br:not(:-moz-last-node) {
    
    position:relative;
    
    left: -1ex
    
  }

  
  #cb-p-tgt {
    font-size: 8pt;
    padding: .4em;
    background-color: #ddd;
    color: #333;
  }
  #cb-p-tgt-can {
    text-decoration: underline;
    color: #36c;
    font-weight: bold;
    margin-left: 2em;
  }
  #cb-p-tgt .spin {
    width: 16px;
    height: 16px;
    background: url(//ssl.gstatic.com/docs/clipboard/spin_16o.gif) no-repeat;
  }
}

h6 { font-size: 8pt }
h5 { font-size: 8pt }
h4 { font-size: 10pt }
h3 { font-size: 12pt }
h2 { font-size: 14pt }
h1 { font-size: 18pt }

blockquote {padding: 10px; border: 1px #DDD dashed }

.webkit-indent-blockquote { border: none; }

a img {border: 0}

.pb {
  border-width: 0;
  page-break-after: always;
  /* We don't want this to be resizeable, so enforce a width and height
     using !important */
  height: 1px !important;
  width: 100% !important;
}

.editor .pb {
  border-top: 1px dashed #C0C0C0;
  border-bottom: 1px dashed #C0C0C0;
}

div.google_header, div.google_footer {
  position: relative;
  margin-top: 1em;
  margin-bottom: 1em;
}


/* Table of contents */
.editor div.writely-toc {
  background-color: #f3f3f3;
  border: 1px solid #ccc;
}
.writely-toc > ol {
  padding-left: 3em;
  font-weight: bold;
}
ol.writely-toc-subheading {
  padding-left: 1em;
  font-weight: normal;
}
/* IE6 only */
* html writely-toc ol {
  list-style-position: inside;
}
.writely-toc-none {
  list-style-type: none;
}
.writely-toc-decimal {
  list-style-type: decimal;
}
.writely-toc-upper-alpha {
  list-style-type: upper-alpha;
}
.writely-toc-lower-alpha {
  list-style-type: lower-alpha;
}
.writely-toc-upper-roman {
  list-style-type: upper-roman;
}
.writely-toc-lower-roman {
  list-style-type: lower-roman;
}
.writely-toc-disc {
  list-style-type: disc;
}

/* Ordered lists converted to numbered lists can preserve ordered types, and
   vice versa. This is confusing, so disallow it */
ul[type="i"], ul[type="I"], ul[type="1"], ul[type="a"], ul[type="A"] {
  list-style-type: disc;
}

ol[type="disc"], ol[type="circle"], ol[type="square"] {
  list-style-type: decimal;
}

/* end default css */


  /* default print css */
  @media print {
    body {
      padding: 0;
      margin: 0;
    }

    div.google_header, div.google_footer {
      display: block;
      min-height: 0;
      border: none;
    }

    div.google_header {
      flow: static(header);
    }

    /* used to insert page numbers */
    div.google_header::before, div.google_footer::before {
      position: absolute;
      top: 0;
    }

    div.google_footer {
      flow: static(footer);
    }

    /* always consider this element at the start of the doc */
    div#google_footer {
      flow: static(footer, start);
    }

    span.google_pagenumber {
      content: counter(page);
    }

    span.google_pagecount {
      content: counter(pages);
    }

    .endnotes {
      page: endnote;
    }

    /* MLA specifies that endnotes title should be 1" margin from the top of the page. */
    @page endnote {
      margin-top: 1in;
    }

    callout.google_footnote {
      
      display: prince-footnote;
      footnote-style-position: inside;
      /* These styles keep the footnote from taking on the style of the text
         surrounding the footnote marker. They can be overridden in the
         document CSS. */
      color: #000;
      font-family: Verdana;
      font-size: 10.0pt;
      font-weight: normal;
    }

    /* Table of contents */
    #WritelyTableOfContents a::after {
      content: leader('.') target-counter(attr(href), page);
    }

    #WritelyTableOfContents a {
      text-decoration: none;
      color: black;
    }

    /* Comments */
    .writely-comment-yellow {
      background-color: #ffffd7;
    }
    .writely-comment-orange {
      background-color: #ffe3c0;
    }
    .writely-comment-pink {
      background-color: #ffd7ff;
    }
    .writely-comment-green {
      background-color: #d7ffd7;
    }
    .writely-comment-blue {
      background-color: #d7ffff;
    }
    .writely-comment-purple {
      background-color: #eed7ff;
    }
  }

  @page {
    @top {
      content: flow(header);
    }
    @bottom {
      content: flow(footer);
    }
    @footnotes {
      border-top: solid black thin;
      padding-top: 8pt;
    }
  }
  /* end default print css */


/* custom css */


/* end custom css */

/* ui edited css */

body {
  font-family: Verdana;
  
  font-size: 10.0pt;
  line-height: normal;
  background-color: #ffffff;
}
/* end ui edited css */


/* editor CSS */
.editor a:visited {color: #551A8B}
.editor table.zeroBorder {border: 1px dotted gray}
.editor table.zeroBorder td {border: 1px dotted gray}
.editor table.zeroBorder th {border: 1px dotted gray}


.editor div.google_header, .editor div.google_footer {
  border: 2px #DDDDDD dashed;
  position: static;
  width: 100%;
  min-height: 2em;
}

.editor .misspell {background-color: yellow}

.editor .writely-comment {
  font-size: 9pt;
  line-height: 1.4;
  padding: 1px;
  border: 1px dashed #C0C0C0
}


/* end editor CSS */

</style>

  
  <title> W3 Komunikacja grupowa</title>

</head>

<body 
    
    >
    
    
    
<div id=xurx style=TEXT-ALIGN:left>
  <font size=5><b style=COLOR:#3d85c6>Komunikacja grupowa</b></font><br>
  <hr size=2><br>
  Wykład omawia teoretyczne podstawy komunikacji grupowej – gałęzi przetwarzania rozproszonego zajmującej się systemami, w których osłabia się założenie o stałej liczbie procesów uczestniczących w przetwarzaniu. Procesy organizowane są w dynamicznie zmieniające się grupy, a wszelka komunikacja odbywa się z uwzględnieniem postrzeganego przez procesy stanu grupy.
  <p>
    Pierwsza część wykładu prezentuje założenia oraz specyfikacje związane z własnościami usługi członkostwa, natomiast w drugiej przedstawione są wybrane algorytmy rozsyłania (ang. <i>multicast</i> ), powszechnie stosowane w komunikacji grupowej.
  </p>
  <br>
  <br>
  <b style=COLOR:#3d85c6><font size=3>Podstawowe definicje</font></b><br>
  <hr size=2><br>
  <div id=lvmc style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2283dsbj9vgp_b.png" style=HEIGHT:340px;WIDTH:500px><br>
    <br>
    <b>Komunikację</b> <b>grupową</b> definiuje się jako mechanizm umożliwiający procesom systemu rozproszonego organizowanie się w sposób dynamiczny w grupy i niezawodną wymianę wiadomości w ramach grupy. Za każdy z tych dwóch aspektów odpowiada odrębny mechanizm: usługa członkostwa zajmuje się zarządzaniem składem grupy (dynamiczne dołączanie i odłączanie procesów z grupy), a usługa rozsyłania dostarcza mechanizmu rozgłaszania wiadomości pomiędzy procesami w grupie zgodnie z przyjętym poziomem niezawodności.
    <p>
      <br>
    </p>
    <p>
      Od strony teoretycznej komunikacja grupowa służy jako narzędzie do modelowania komunikacji o podwyższonym poziomie niezawodności (w skrócie - komunikacji niezawodnej) pomiędzy procesami przy zmieniającym się zbiorze uczestniczących w przetwarzaniu procesów.
    </p>
    <p>
      <br>
    </p>
    <p>
      Systemy komunikacji grupowej GCS (od nazwy angielskiej <i>Group</i> <i>Communication</i> <i>System</i> ) powszechnie wykorzystuje się w aplikacjach, które potrzebują skorzystać na niższym poziomie z mechanizmów łączenia procesów w grupy oraz niezawodnej komunikacji pomiędzy procesami w grupie. Wśród przykładowych zastosowań można wymienić: systemy konferencyjne, gry sieciowe czy systemy o podwyższonej niezawodności, wykorzystujące zwielokrotnianie (ang. <i>replication</i> ).
    </p>
    <br>
    <br>
    <div id=via: style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2284fxdsrhcd_b.png" style=HEIGHT:341px;WIDTH:500px><br>
      <br>
      Model systemu zakłada, że procesy organizowane są w grupy oraz że komunikacja pomiędzy procesami ma charakter grupowy.<br>
      <br>
      <p>
        <b>Grupa</b> to rzeczywisty zbiór procesów, uczestniczących w danej chwili we wspólnym przetwarzaniu (np. obliczenia inżynierskie, systemy medyczne czy militarne) i komunikujących się poprzez przekazywanie wiadomości (ang. <i>message</i> <i>passing</i> ). <b>Obraz</b> <b>grupy</b> to z kolei stan grupy widziany w danej chwili czasu rzeczywistego w procesie.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Obraz grupy może się znacząco różnić od rzeczywistej grupy, a ponadto obrazy grupy mogą być różne w różnych procesach. W przykładzie na rysunku, proces <i>q</i> ulega awarii, co z punktu widzenia komunikacji grupowej oznacza opuszczenie grupy. W obrazie procesu <i>r</i> proces <i>q</i> opuścił już grupę, zaś w obrazie procesu <i>p</i> – jeszcze nie, a przez to obrazy procesów <i>p</i> i <i>r</i> są różne.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Należy podkreślić, że <i>z</i> <i>punktu</i> <i>widzenia</i> <i>aplikacji</i> <i>nie</i> <i>rozróżnia</i> <i>się</i> <i>awarii</i> <i>procesu</i> <i>od</i> <i>jawnego</i> <i>opuszczenia</i> <i>przez</i> <i>niego</i> <i>grupy</i> – obydwa te przypadki są aplikacji przedstawiane po prostu jako opuszczenie grupy.
      </p>
      <br>
      <br>
      <b style=COLOR:#3d85c6><font size=3>Model matematyczny</font></b><br>
      <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-3-wyk-2.0-Slajd2 title=Sr-3-wyk-2.0-Slajd2> </a><br>
    </div>
    <div id=isk8 style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2285frjs6gdk_b.png" style=HEIGHT:340px;WIDTH:500px><br>
      <br>
      W definicjach specyfikacji wystąpią następujące zbiory:<br>
      <br>
      <p>
        P – zbiór procesów w systemie;<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        M – zbiór wiadomości przesyłanych w systemie;<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        VID – zbiór identyfikatorów obrazów grup.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Wyróżnia się następujące elementarne zdarzenia w systemie:<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        <b>wyślij(p</b> , m) – proces <i>p</i> wysyła wiadomość <i>m</i>&nbsp;; zauważmy, że nie określa się odbiorcy, gdyż wiadomość wysyłana jest do całej grupy<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        <b>odbierz(p</b> , m) – proces <i>p</i> odbiera wiadomość <i>m</i>&nbsp;; nadawca wiadomości może być określony, ale tutaj dla uproszczenia nie jest;<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        <b>zmiana_obrazu(p</b> , &lt;id, członkowie&gt;) – w procesie <i>p</i> następuje zmiana obrazu; nowy obraz o identyfikatorze <i>id</i> zawiera procesy<br>
      </p>
      <p>
        określone zmienną <i>członkowie</i> . Sam obraz zaś jest parą (<i>id</i> , <i>członkowie</i> ), obejmującą globalny identyfikator obrazu i należące do niego procesy. Dwa obrazy V i V’ są więc równe wtedy i tylko wtedy, gdy równe są ich identyfikatory oraz zbiory procesów.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        <b>awaria(p</b> ) – proces <i>p</i> ulega awarii<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        <b>powrót(p</b> ) – proces <i>p</i> wznawia działanie po awarii<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        <br>
      </p>
      <p>
        <b style=COLOR:#3d85c6><font size=3>Architektura systemu</font></b><br>
      </p>
      <hr size=2><br>
      <div id=n6o. style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2286p7df5khb_b.png" style=HEIGHT:341px;WIDTH:500px>
      </div>
      <br>
    </div>
    <p>
      Oprogramowanie realizujące komunikację grupową stanowi warstwę usługową dla aplikacji, stąd znajduje się poniżej aplikacji. Wejściowe zdarzenie <i>wyślij</i> zachodzi z inicjatywy aplikacji, zgłaszającej wysłanie wiadomości do grupy. Wyjściowe zdarzenia <i>odbierz</i> i <i>zmiana_obrazu</i> są natomiast zgłaszane przez warstwę komunikacji grupowej. Wejściowe zdarzenia <i>awaria</i> i <i>powrót</i> zgłasza detektor uszkodzeń, którego istnienie i poprawne działanie tutaj zakładamy.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Warstwa komunikacji grupowej, realizująca system komunikacji grupowej, jest zazwyczaj złożona z wielu podwarstw, realizujących takie funkcje, jak np. wspomniane już zarządzanie grupami (ang. <i>membership</i> ), rozsyłanie (ang. <i>multicast</i> ), funkcje wznawiania pracy procesu po awarii, uzgadnianie i inne. Na styku z aplikacją dostarcza jednak przejrzystego interfejsu, dzięki czemu projekt i implementacja aplikacji są znacząco uproszczone.
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Predykaty</font></b><br>
    <hr size=2><br>
    <div id=csb5 style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2287hj486ndb_b.png" style=HEIGHT:342px;WIDTH:500px><br>
      <br>
      Powyższe predykaty budowane są na podstawie elementarnych zdarzeń, przedstawionych wcześniej.<br>
      <br>
      <p>
        Predykat <i>obraz_w_chwili</i> definiuje obraz, jaki w procesie p istnieje w chwili zajścia zdarzenia ti.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Predykat <i>odbiera</i> zachodzi, gdy proces p odbierze wiadomość m w dowolnej chwili. Predykat <i>odbiera_w</i> określa dodatkowo, w jakim obrazie proces <i>p</i> odbiera wiadomość <i>m</i> .<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Predykat <i>wysyła</i> jest prawdą, jeśli proces <i>p</i> wysłał wiadomość <i>m</i> w dowolnej chwili.
      </p>
      <br>
      <br>
      <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-3-wyk-2.0-Slajd5 title=Sr-3-wyk-2.0-Slajd5> </a>
      <div id=w-bq style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2288fwbrndhq_b.png" style=HEIGHT:343px;WIDTH:500px><br>
        <br>
        <p>
          Predykat <i>wysyła_w</i> jest prawdziwy, gdy proces <i>p</i> wyśle wiadomość <i>m</i> w konkretnym obrazie <i>V</i> .
        </p>
        <p>
          <br>
        </p>
        <p>
          Predykat <i>instaluje</i> zostaje spełniony, gdy proces <i>p</i> zmieni obraz grupy na <i>V</i> .<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          Predykat <i>instaluje_w</i> oznacza zmianę obrazu z dotychczasowego <i>V</i> <i>’</i> na nowy, <i>V</i> . Zmiana obrazu może być spowodowana dołączeniem lub odłączeniem pewnego zbioru procesów do- lub z grupy. Należy pamiętać, że odłączenie procesu modeluje jego faktyczne odłączenie po zakończeniu obliczeń albo awarię, wykrytą i zgłoszoną przez detektor uszkodzeń.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          Ponieważ predykat <i>instaluje_w</i> uwzględnia poprzedni obraz grupy, jest szczególnie przydatny w tych własnościach, które uwzględniają historyczne obrazy w procesie (najczęściej tylko poprzedni); przykładem takiej własności jest wirtualna synchronizacja, omówiona w dalszej części.
        </p>
        <br>
        <br>
        <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-3-wyk-2.0-Slajd6 title=Sr-3-wyk-2.0-Slajd6> </a>
        <div id=y3m- style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2289gzxw8mgk_b.png" style=HEIGHT:342px;WIDTH:500px><br>
          <br>
          <p>
            Predykat <i>awaria_w</i> zachodzi wówczas, gdy awaria procesu <i>p</i> nastąpi w chwili, gdy w procesie tym pamiętany jest obraz grupy <i>V</i>.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            O bezpośrednim poprzedzaniu i następstwie zdarzeń w jednym procesie mówią predykaty <i>następne_zdarzenie</i> i <i>poprzednie_zdarzenie</i>.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Przedstawione predykaty posłużą w dalszej części prezentacji do definiowania różnych własności systemów komunikacji grupowej.
          </p>
          <br>
          <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-3-wyk-2.0-Slajd7 title=Sr-3-wyk-2.0-Slajd7> </a><br>
          <b style=COLOR:#3d85c6><font size=3>Założenia odnośnie środowiska</font></b><br>
          <hr size=2><br>
        </div>
        <div id=j-qt style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2290cv8nfrfs_b.png" style=HEIGHT:342px;WIDTH:500px><br>
          <br>
          Założenie o integralności wykonania (ang. <i>execution</i> <i>integrity</i> ) wymaga, by pomiędzy zdarzeniami <b>awaria</b> i <b>powrót</b> w jednym procesie nie następowało żadne inne zdarzenie. Innymi słowy, przyjmuje się model awarii znany pod nazwą awaria-wznowienie (ang. <i>crash-recovery</i> ). W modelu tym, w odróżnieniu od modelu awarii bizantyjskich, przyjmuje się, że proces po awarii nie wykonuje żadnych akcji (np. nie wysyła i nie odbiera wiadomości).<br>
          <br>
          <p>
            W jeszcze prostszym modelu awarii, nazywanym modelem „awaria-stop” (ang. <i>fail-stop</i> ) nie dopuszcza się nawet wznowienia pracy po awarii – proces, który jej uległ, przestaje działać na zawsze. W uproszczeniu można powiedzieć, że różnica pomiędzy modelami awaria-wznowienie i awaria-stop polega na tym, że w tym drugim nie ma zdarzenia powrotu z awarii i wznowienia pracy procesu.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Założenie o unikalności wiadomości wymaga, by każda wiadomość <i>m</i> była niepowtarzalna; najczęściej osiąga się to poprzez przypisanie każdej wiadomości unikalnego identyfikatora wiadomości, złożonego na przykład z identyfikatora nadawcy połączonego z numerem sekwencyjnym lub znacznikiem czasowym. Dzięki temu założeniu można wymagać, by każda wiadomość w systemie była wysłana najwyżej jeden raz.
          </p>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Usługa członkostwa - własności</font></b><br>
          <hr size=2><br>
          <div id=q3ky style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2291gx5x59hn_b.png" style=HEIGHT:343px;WIDTH:500px><br>
            <br>
            Przez <b>własność</b> należy rozumieć gwarancję dostarczaną przez system. Oczywiście w różnych systemach dostępne są różne gwarancje, zależne od decyzji twórców systemu.<br>
            <br>
            <p>
              Własność <b>samozawierania</b> (ang. <i>self</i> <i>inclusion</i> ) mówi, że dany proces powinien należeć do własnego obrazu grupy. Ponieważ każdy proces zawsze jest w stanie komunikować się z sobą samym, gwarancji tej dostarczają wszystkie znane systemy komunikacji grupowej.
            </p>
            <p>
              Własność <b>monotoniczności</b> <b>lokalnej</b> (ang. <i>local</i> <i>monotonicity</i> ) wymaga, by identyfikator danego obrazu grupy był większy od identyfikatorów wcześniejszych obrazów.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Własność <b>początkowego</b> <b>obrazu</b> (ang. <i>initial</i> <i>view</i> <i>event</i> ) wymaga zaś, by każde wysłanie lub odbiór wiadomości następowało w pewnym obrazie. W szczególności oznacza to, że na samym początku przetwarzania musi w procesie istnieć pewien obraz grupy.
            </p>
            <br>
            <br>
          </div>
          <div id=uw__ style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2292cndgdgdc_b.png" style=HEIGHT:343px;WIDTH:500px>
          </div>
          <br>
          Własności <b>braku</b> <b>samogeneracji</b> (ang. <i>delivery</i> <i>integrity</i> ) oraz <b>braku</b> <b>powielania</b> (ang. <i>no</i> <i>duplication</i> ) stawiają wymagania kanałom komunikacyjnym. Pierwsza z nich stanowi, że każda odebrana wiadomość musi mieć swojego nadawcę, który wcześniej ją wysłał. Innymi słowy, kanał sam z siebie nie może wygenerować wiadomości, bo z punktu widzenia systemu pojawiłaby się ona „znikąd”. Druga zaś własność wymaga, by jeden proces nie mógł odebrać danej wiadomości więcej, niż jeden raz.<br>
          <br>
          <br>
          <div id=w46g style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2293g5xgmsgc_b.png" style=HEIGHT:341px;WIDTH:500px>
          </div>
          <br>
        </div>
      </div>
    </div>
    Własność 3, <b>dostarczenia</b> <b>w</b> <b>obrazie</b> <b>z</b> <b>momentu</b> <b>wysłania</b> (ang. <i>sending</i> <i>view</i> <i>delivery</i> ), wymaga, by wiadomość została dostarczona do wszystkich odbierających ją procesów w tym samym obrazie, w którym została wysłana. Oznacza to, że pomiędzy zdarzeniem wysłania a zdarzeniem dostarczenia do ostatniego procesu nie mogła zajść żadna zmiana w obrazie grupy, w szczególności więc również awaria dowolnego procesu. Należy podkreślić, że własność ta (podobnie jak własność 4) nie wymaga dostarczenia wiadomości do wszystkich procesów w grupie. Można ją wyrazić inaczej w sposób następujący: <i>jeśli</i> proces <i>q</i> dostarcza wiadomość <i>m</i> , to odbiera ją <i>na</i> <i>pewno</i> w tym samym obrazie, w którym wysłał ją proces <i>p</i>.<br>
    <br>
    <p>
      Słabsza własność 4, <b>dostarczenie</b> <b>w</b> <b>tym</b> <b>samym</b> <b>obrazie</b> (ang. <i>same</i> <i>view</i> <i>delivery</i> ), nie wymaga już, by obraz w procesie odbierającym był równy obrazowi z momentu wysłania. Nadal jednak wymaga, by obrazy wszystkich procesów odbierających były sobie równe.
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Własność 3 - przykład</font></b><br>
    <hr size=2><br>
    <div id=dnzp style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2294fs496pdh_b.png" style=HEIGHT:342px;WIDTH:500px><br>
      <br>
      W przykładzie na rysunku dla wiadomości <i>m</i> zagwarantowano własność dostarczenia w obrazie z momentu wysłania, gdyż została dostarczona do odbierających ją procesów w tym samym obrazie, w którym proces <i>r</i> ją wysłał. W przykładzie odbierają ją wszystkie procesy należące do obrazu, choć przypomnijmy, że nie musiałoby tak być – ważne jest tylko, by w odbierających procesach dostarczenie wiadomości nastąpiło w tym samym obrazie, w którym zaszło wysłanie.<br>
      <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-3-wyk-2.0-Slajd12 title=Sr-3-wyk-2.0-Slajd12> </a><br>
      <br>
      <b style=COLOR:#3d85c6><font size=3>Własność 4 - przykład</font></b><br>
      <hr size=2><br>
      <div id=qruw style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2295d5dv25gb_b.png" style=HEIGHT:343px;WIDTH:500px>
      </div>
      <br>
    </div>
    Dla wiadomości <i>m</i> <i>’</i> natomiast zagwarantowano własność dostarczenia w tym samym obrazie – dostarczenie zachodzi w momencie, gdy wszystkie odbierające procesy mają ten sam obraz, choć nie jest to już ten sam obraz, w którym wysyłano wiadomość.<br>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Usługa rozsyłania - własności (3)</font></b><br>
    <hr size=2><br>
    <div id=p6_w style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2296c47jdhhq_b.png" style=HEIGHT:343px;WIDTH:500px><br>
      <p>
        <br>
        Najpopularniejsza we współczesnych systemach komunikacji grupowej jest własność <b>wirtualnej</b> <b>synchronizacji</b> (ang. <i>virtual</i> <i>synchrony</i> lub <i>view</i> <i>synchrony</i> ). Wymaga ona, by wszystkie procesy, które ze starego obrazu <i>V</i> <i>’</i> przechodzą do nowego obrazu <i>V</i> , dostarczyły przed zainstalowaniem nowego obrazu (czyli jeszcze w starym) każdą wiadomość, którą dostarczył choć jeden proces. Innymi słowy, wymaga się od procesów dostarczania tych samych zbiorów wiadomości w tych samych obrazach. Intuicyjnie oznacza to, że procesy są synchronizowane kolejnymi zmianami obrazów – zmiana obrazu jest barierą, której proces nie może przekroczyć, jeśli nie odebrał wymaganych wiadomości.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Własność ta jest bardzo przydatna na przykład w systemach rozproszonych wykorzystujących zwielokrotnianie, w których kopie danego obiektu najczęściej tworzą grupę. Wiele modeli spójności na niższym poziomie wymaga zachowania pewnych gwarancji komunikacji grupowej, w tym często właśnie wirtualnej synchronizacji.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Należy jeszcze podkreślić zasadniczą różnicę pomiędzy wirtualną synchronizacją a własnościami dostarczenia w obrazie z momentu wysłania czy dostarczenia w tym samym obrazie.. Otóż wirtualna synchronizacja stawia wymagania wszystkim procesom zmieniającym obraz, co w praktyce najczęściej oznacza wszystkie procesy w grupie.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Można ponadto zauważyć, że wirtualna synchronizacja jest ściśle silniejsza od własności dostarczenia w tym samym obrazie, natomiast jest nieporównywalna z własnością dostarczenia w obrazie z momentu wysłania.
      </p>
      <br>
      <br>
      <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-3-wyk-2.0-Slajd14 title=Sr-3-wyk-2.0-Slajd14> </a><font size=3><b style=COLOR:#3d85c6>Wirtualna synchronizacja - przykład</b></font><br>
      <hr size=2><br>
    </div>
    <div id=bqs8 style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2297fq3txsfg_b.png" style=HEIGHT:339px;WIDTH:500px><br>
      <br>
      W przedstawionym przykładzie, dla wiadomości <i>m</i> zachowana jest własność dostarczenia w obrazie z momentu wysłania (odbierające procesy <i>p</i> i <i>q</i> dostarczają wiadomość w obrazie 1, w którym została ona wysłana), a tym samym własność dostarczenia w tym samym obrazie (wszystkie odbierające procesy dostarczają wiadomość w tym samym obrazie), nie jest natomiast zachowana własność wirtualnej synchronizacji, gdyż nie wszystkie procesy zmieniające obraz grupy ją dostarczyły.<br>
      <br>
      <p>
        Dla wiadomości <i>m</i> <i>’</i> zachowano każdą z trzech własności. W przypadku wiadomości <i>m</i> <i>’’</i> zaś nie jest zachowana żadna z trzech własności, gdyż proces <i>p</i> dostarcza tę wiadomość w innym obrazie, niż pozostałe procesy.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Należy zaznaczyć, że zazwyczaj należy dostarczać tylko jednej konkretnej gwarancji, zależnej od wymagań aplikacji w zakresie niezawodności. Ponieważ jednak celem rysunku jest ukazanie różnic pomiędzy wspomnianymi własnościami, wspomina się dla każdej wiadomości o każdej własności.
      </p>
      <br>
      <br>
      <font size=3><b style=COLOR:#3d85c6>Przykładowe systemy</b></font><br>
      <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-3-wyk-2.0-Slajd15 title=Sr-3-wyk-2.0-Slajd15> </a><br>
    </div>
    <div id=jzhm style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2298gt72b2c7_b.png" style=HEIGHT:342px;WIDTH:500px>
    </div>
    <br>
    Wymienione tu projekty to przykłady popularnych systemów komunikacji grupowej, nazywanych skrótowo systemami GCS (ang. <i>Group</i> <i>Communication</i> <i>System</i> ). Są one realizowane jako warstwa pośrednia oprogramowania (ang. <i>middleware</i> ), oferująca usługi w zakresie zarządzania grupami i niezawodnej komunikacji w grupach. Dwa z nich zostaną omówione bardziej szczegółowo na kolejnych slajdach. Opis oraz rysunki oparto na pracy „A Step Towards a New Generation of Group Communication Systems”, wymienionej w bibliografii.<br>
    <br>
    <br>
    <font size=3><b style=COLOR:#3d85c6>System Isis</b></font><br>
    <hr size=2><br>
    <div id=qwfy style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2299cdgqqphh_b.png" style=HEIGHT:342px;WIDTH:500px>
    </div>
    <br>
    <p>
      Isis jest pierwszym systemem, w którym zaproponowano wyodrębnienie mechanizmów komunikacji grupowej. Należy do grupy systemów monolitycznych, czyli niemodularnych, a więc takich, w których architektura jest stała i nie może być dostosowana do konkretnych potrzeb aplikacji. Oczywistą wadą takich systemów jest konieczność dostosowania aplikacji do nich oraz konieczność użycia wszystkiego, co oferuje system – nawet, jeśli byłoby to zbędne i skutkowało spadkiem efektywności pracy.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Ponadto, Isis jest systemem zgodnym z modelem głównej partycji (ang. <i>primary</i> <i>partition</i> ), co oznacza, że przy podziale sieci przetwarzanie jest kontynuowane tylko w głównym jej fragmencie, w tak zwanej głównej partycji. W szczególności oznacza to, że wszystkie procesy głównej partycji otrzymują taką samą sekwencję obrazów grupy.
    </p>
    <br>
    <br>
    <font size=3><b style=COLOR:#3d85c6>Architektura systemu Isis</b></font><br>
    <hr size=2><br>
    <div id=fmia style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2300dnbvnjhn_b.png" style=HEIGHT:345px;WIDTH:500px><br>
      <br>
      <b>Warstwa</b> <b>członkostwa</b> jest odpowiedzialna za zarządzanie składem grupy, obejmujące monitorowanie wykrywanie zdarzeń <i>leave</i> , oznaczających opuszczenie grupy (na skutek zakończenia przetwarzania lub awarii procesu) oraz obsługę zdarzeń <i>join</i> dołączenia do niej nowego procesu. Warstwa ta zapewnia procesom dostarczanie nowych obrazów grupy w takiej samej kolejności, w <i>całkowitym</i> uporządkowaniu (ang. <i>total</i> <i>order</i> ).<br>
      <br>
      <p>
        Warstwa członkostwa nie dostarcza jednak żadnych mechanizmów komunikacyjnych. Z tego powodu została rozszerzona o warstwę <b>wirtualnej</b> <b>synchronizacji</b> , realizującą rozgłaszanie wiadomości do aktualnych członków grupy.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Najwyższa warstwa, <b>rozgłaszania</b> <b>atomowego</b> , zapewnia, że wiadomości aplikacyjne są dostarczane w tej samej kolejności przez wszystkie procesy. Rozgłaszanie atomowe jest tutaj zrealizowane w oparciu o znajdującą się niżej warstwę wirtualnej synchronizacji.
      </p>
      <br>
      <br>
      <font size=3><b style=COLOR:#3d85c6>System Horus/Ensemble</b></font><br>
      <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-3-wyk-2.0-Slajd18 title=Sr-3-wyk-2.0-Slajd18> </a><br>
    </div>
    <div id=usyl style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2301d8scgztv_b.png" style=HEIGHT:341px;WIDTH:500px><br>
      <br>
    </div>
    System Horus, czy jego wersja zaimplementowana w języku OCaml i znana pod nazwą Ensemble, jest następcą systemu Isis. Jako system modularny, niemonolityczny, pozwala użytkownikowi wybrać tylko te funkcje, których on potrzebuje. Ponadto, jest zgodny z modelem wielu partycji (ang. <i>partitionable</i> <i>membership</i> ), co oznacza, że po podziale sieci dopuszcza się kontynuowanie przetwarzania w różnych jej fragmentach.<br>
    <br>
    <br>
    <font size=3><b style=COLOR:#3d85c6>Architektura systemu Horus</b></font><br>
    <hr size=2><br>
    <div id=c3-q style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2302fpxtmsdk_b.png" style=HEIGHT:342px;WIDTH:500px><br>
      <br>
      Na rysunku przedstawiono przykładowy stos protokołów systemu Horus:<br>
      <br>
      <p>
        Należy zaznaczyć, że informacje o zdarzeniach w systemie Horus przekazywane są <i>w</i> <i>górę</i> <i>stosu</i> , począwszy od najniżej działającej warstwy. Warstwa generująca dane zdarzenie propaguje je najpierw w dół stosu, a następnie informacja o nim „odbija się” od najniższej warstwy i wędruje w górę, do najwyższej.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Komponent <i>Niezawodne</i> <i>FIFO</i> realizuje kanały komunikacyjne, zachowujące uporządkowanie wiadomości FIFO, polegające na dostarczaniu wiadomości od danego nadawcy zgodnie z kolejnością ich wysłania przez tego nadawcę (szerzej omówiono to zagadnienie w drugiej części wykładu, poświęconej wybranym algorytmom komunikacji grupowej).<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Warstwa <i>Stabilność</i> zajmuje się sprawdzaniem, czy wiadomości na danym poziomie zostały odebrane przez wszystkie procesy w grupie. O takich wiadomościach mówi się, że są <i>stabilne</i> . Wiadomości stabilne wykorzystuje się w aplikacjach wymagających wysokiej niezawodności przy dostarczaniu wiadomości, na przykład do zaimplementowania wirtualnej synchronizacji. Najczęściej stabilne wiadomości zostają trwale zapisane, by mogły przetrwać ewentualną awarię maszyny lub aplikacji i zostać dostarczone po wznowieniu pracy. Warstwa Stabilność może zostać umieszczona w wielu miejscach stosu; wybór jej lokalizacji ma jednak wpływ na efektywność pracy.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Warstwa <i>rozgłaszania</i> <i>atomowego</i> porządkuje wiadomości, ale robi to tylko w sytuacjach bezawaryjnych. Gdyby więc nie skorzystano z dodatkowych komponentów odpowiedzialnych za detekcję uszkodzeń i członkostwo, wówczas różne algorytmy rozgłaszania atomowego blokowałyby się w przypadku awarii lub podziału sieci.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Co ważne, <i>aplikacja</i> <i>nie</i> <i>jest</i> umieszczona w najwyższej warstwie. Dzieje się tak z przyczyn wydajnościowych – gdyby aplikacja była na samej górze, dostarczanie do niej informacji o zachodzących zdarzeniach trwałoby dłużej. Bardziej efektywnym rozwiązaniem jest umieszczenie komponentów aktywnych w <i>normalnych</i> sytuacjach poniżej aplikacji, a komponentów aktywnych w <i>nadzwyczajnych</i> sytuacjach, które są rzadziej wykorzystywane, powyżej aplikacji.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Warstwa <i>Sync</i> blokuje procesy podczas zmiany obrazu grupy, a warstwa <i>członkostwa</i> <i>i</i> <i>wirtualnej</i> <i>synchronizacji</i> dostarcza mechanizmów zarządzania grupą i wirtualnej synchronizacji.
      </p>
      <br>
      <br>
      <font size=3><b style=COLOR:#3d85c6>Algorytmy niezawodnej komunikacji grupowej</b></font><br>
      <hr size=2>
    </div>
    <br>
    <div id=av9x style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2303dc38rjdt_b.png" style=HEIGHT:343px;WIDTH:500px><br>
      <br>
      Druga część wykładu dotyczy algorytmów niezawodnego rozsyłania (ang. <i>multicast</i> ) wiadomości pomiędzy procesami w grupie. Omówione zostaną podstawowe algorytmy: niezawodne rozesłanie bez dodatkowych gwarancji na kolejność wiadomości (RB), niezawodne rozesłanie z dodatkową gwarancją uporządkowania FIFO (FIFO-RB), niezawodne rozesłanie z gwarancją uporządkowania przyczynowego wiadomości (Przyczynowy-RB) oraz niezawodne rozesłanie atomowe.<br>
      <br>
      <p>
        Dla każdego algorytmu dopuszcza się awarie procesów oraz kanałów komunikacyjnych. Szczegółowe założenia będą podane przy konkretnych algorytmach.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        W dalszej części prezentacji terminy „rozesłanie” i „rozgłoszenie” są używane zamiennie i oznaczają to samo – wysłanie wiadomości do wszystkich procesów w grupie.
      </p>
      <br>
      <br>
      <font size=3><b style=COLOR:#3d85c6>Własności niezawodnego rozgłoszenia</b></font><br>
      <hr size=2>
    </div>
    <br>
    <div id=k5wr style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2304hm8v9wc2_b.png" style=HEIGHT:344px;WIDTH:500px><br>
      <br>
      Zadaniem algorytmu <b>niezawodnego</b> <b>rozgłaszenia</b> (ang. <i>Reliable</i> <i>Broadcast</i> <i>–</i> <i>RB</i> ) jest dostarczenie wiadomości wszystkim poprawnym procesom (tzn. procesom, które na pewno nie ulegną awarii w trakcie przebiegu algorytmu) pomimo awarii innych procesów lub kanałów komunikacyjnych. Specyfikacja algorytmu obejmuje następujące własności:<br>
      <br>
      <p>
        <i>Ważność</i> – wymaga, by jeśli poprawny proces rozgłosił wiadomość, wszystkie poprawne procesy w skończonym czasie dostarczyły tę wiadomość.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        <i>Zgodność</i> – wymaga, by jeśli choć jeden poprawny proces dostarczył wiadomość, wszystkie procesy dostarczyły tę wiadomość, nawet jeśli proces nadawcy był niepoprawny (np. uległ awarii podczas rozsyłania i nie zdołał wiadomości wysłać do wszystkich procesów).
      </p>
      <p>
        <br>
      </p>
      <p>
        <i>Integralność</i> – wymaga, by daną wiadomość każdy proces dostarczył najwyżej jeden raz i to pod warunkiem, że została ona wcześniej rozgłoszona przez jakiś (niekoniecznie poprawny) proces.
      </p>
      <br>
      <br>
      <font size=3><b style=COLOR:#3d85c6>Algorytm RB - założenia</b></font><br>
      <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-3-wyk-2.0-Slajd22 title=Sr-3-wyk-2.0-Slajd22> </a><br>
      <div id=vum. style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2305fmx8vnfn_b.png" style=HEIGHT:342px;WIDTH:500px><br>
        <br>
        <b>Uwaga</b>&nbsp;: W dalszej części prezentacji wyróżniamy dwa zdarzenia odbioru wiadomości, wykorzystane w przedstawianych algorytmach:<br>
        <br>
        <p>
          <b>odbierz</b> – wiadomość została już odebrana przez podwarstwę komunikacji grupowej, ale jeszcze nie przez proces<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          <b>dostarcz</b> – wiadomość odbiera proces/aplikacja.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          Ponadto, przez <b>rozgłoś(T</b> , m) i <b>dostarcz(T</b> , m) oznaczamy dwie elementarne operacje związane z rozgłoszeniem typu T (R – niezawodne, F – FIFO, C – przyczynowe, A – atomowe).
        </p>
        <br>
        <br>
        <font size=3><b style=COLOR:#3d85c6>Algorytm RB dla procesu <i>p</i></b></font><br>
        <hr size=2><br>
        <div id=zudz style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2306cm8ckg3r_b.png" style=HEIGHT:342px;WIDTH:500px>
        </div>
      </div>
      <br>
    </div>
    Ideą algorytmu jest, by natychmiast po odebraniu wiadomości przez warstwę komunikacji grupowej, rozgłosić ją do wszystkich procesów w grupie, a dopiero potem dostarczyć procesowi aplikacyjnemu. Takie ponowne rozgłoszenie ma na celu umożliwić dalszą propagację wiadomości pomimo awarii w innych procesach, a w szczególności – w procesie nadawcy.<br>
    <br>
    <p>
      Należy podkreślić, że dla poprawnego działania algorytmu potrzebne jest, by do każdej wiadomości proces nadawcy dołączał swój identyfikator oraz numer sekwencyjny wiadomości; te dwa parametry tworzą razem unikalny identyfikator wiadomości.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      <b>Twierdzenie</b>&nbsp;: Przy założeniu, że w systemie każde dwa poprawne procesy są połączone przez ścieżkę poprawnych łączy i procesów, można udowodnić, że algorytm RB realizuje niezawodne rozgłoszenie w takim systemie.
    </p>
    <br>
    <br>
    <font size=3><b style=COLOR:#3d85c6>Algorytm RB - sytuacja standardowa</b></font><br>
    <hr size=2><br>
    <div id=vc4b style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2307fsdj55fm_b.png" style=HEIGHT:343px;WIDTH:500px><br>
      <br>
      Jak widać na rysunku, dostarczenie wiadomości do każdego procesu następuje jeden raz; późniejsze zdarzenia odebrania wiadomości nie skutkują jej dostarczeniem. W sytuacji, gdy nie zachodzi żadna awaria, dodatkowe komunikaty nie wnoszą nic do algorytmu, natomiast zwiększają złożoność komunikacyjną. Podniesienie poziomu niezawodności odbywa się więc kosztem zwiększenia złożoności komunikacyjnej i czasowej.<br>
      <br>
      <br>
      <font size=3><b style=COLOR:#3d85c6>Algorytm RB - zaginięcie komunikatu</b></font><br>
      <hr size=2><br>
      <div id=c.-k style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2308gwh2h2gn_b.png" style=HEIGHT:341px;WIDTH:500px>
      </div>
      <br>
    </div>
    Rysunek uwidacznia, jak algorytm RB gwarantuje dostarczenie wiadomości, pomimo awarii kanału komunikacyjnego między procesami <i>p</i> i <i>r</i> – wiadomość dociera do procesu r dzięki temu, że ponownie rozgłasza ją proces <i>q</i> .<br>
    <br>
    <br>
    <font size=3><b style=COLOR:#3d85c6>Algorytm FIFO-RB - specyfikacja</b></font><hr size=2><br>
    <div id=ci:q style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2309kkkvvsgc_b.png" style=HEIGHT:341px;WIDTH:500px>
    </div>
    <br>
    <p>
      Porządek <b>FIFO</b> wymaga, by wiadomości wysyłane przez dany proces były dostarczane do odbiorców w takiej samej kolejności, w jakiej wysyłał je ten proces. Do zagwarantowania tego wystarcza numerowanie w procesie nadawcy wysyłanych przez niego wiadomości.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Algorytm FIFO-RB to taki algorytm niezawodnego rozgłaszania, który dodatkowo gwarantuje uporządkowanie FIFO wiadomości. Algorytm FIFO-RB korzysta na niższym poziomie z algorytmu RB.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Studentowi pozostawia się jako ćwiczenie podanie przykładu przebiegu przestrzenno-czasowego, w którym zostanie naruszone uporządkowanie FIFO.
    </p>
    <br>
    <br>
    <font size=3><b style=COLOR:#3d85c6>Algorytm FIFO-RB</b></font><br>
    <hr size=2><br>
    <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-3-wyk-2.0-Slajd27 title=Sr-3-wyk-2.0-Slajd27> </a>
    <div id=yapj style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2310hbkgzkgn_b.png" style=HEIGHT:343px;WIDTH:500px><br>
      <br>
      Niezawodne rozgłaszanie w algorytmie FIFO-RB polega na rozgłoszeniu zgodnym z algorytmem RB. Należy pamiętać, że każda wiadomość posiada numer sekwencyjny, nadany jej przed wysłaniem przez nadawcę.<br>
      <br>
      <p>
        Zanim wiadomość zostanie dostarczona zgodne z uporządkowaniem FIFO, najpierw następuje niezawodne dostarczenie jej przez działający poniżej algorytm RB. Następnie sprawdza się, czy dana wiadomość jest <i>oczekiwaną</i> wiadomością, tzn. czy jest <i>kolejną</i> wiadomością, której proces odbierający spodziewa się od danego nadawcy. Fakt, że dana wiadomość jest kolejną, stwierdza się po wartości towarzyszącego jej numeru sekwencyjnego – powinien on być o jeden większy, niż pamiętany w procesie odbiorcy.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Zmienna <i>worek</i> pamięta wszystkie te wiadomości, które zostały już dostarczone przez algorytm RB, ale jeszcze nie zostały dostarczone przez algorytm FIFO-RB.
      </p>
      <p>
        W tablicy <i>następna</i> są zaś pamiętane numery sekwencyjne odpowiadające poszczególnym procesom-nadawcom w grupie.
      </p>
      <p>
        <br>
      </p>
      <p>
        /*zbiór wiadomości, które <i>p</i> R-dostarczył, ale jeszcze nie F-dostarczył*/<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        /* numer sekwencyjny następnej wiadomości, którą <i>p</i> F-dostarczy*/
      </p>
      <br>
      <br>
      <font size=3><b style=COLOR:#3d85c6>Relacja poprzedzania przyczynowego</b></font><br>
      <hr size=2><br>
      <div id=iwap style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2311czgjh3d2_b.png" style=HEIGHT:341px;WIDTH:500px><br>
        <br>
        <b>Relacja</b> <b>poprzedzania</b> <b>przyczynowego</b> , nazywana również porządkiem przyczynowym, bierze swoją nazwę od angielskiej nazwy <i>Causal</i> <i>Order</i> . Formalna definicja relacji poprzedzania przyczynowego jest następująca:<br>
        <br>
        <p>
          Zdarzenie tj jest przyczynowo zależne od zdarzenia ti (lub inaczej – ti poprzedza tj), gdy:<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          - obydwa te zdarzenia zachodzą w tym samym procesie i ti wystąpiło wcześniej niż tj, lub<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          - ti jest zdarzeniem wysłania wiadomości, a tj jest - zdarzeniem jej odebrania, lub<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          - gdy pomiędzy zdarzeniami ti a tj zachodzi inne zdarzenie, tk, takie że poprzedza je ti, ale jednocześnie ono samo poprzedza tj.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          Ostatni warunek w powyższej definicji ma charakter rekurencyjny. Zdarzeń pośredniczących pomiędzy ti a tj może być wiele, ale relacja poprzedzania przyczynowego może zachodzić pomiędzy kolejnymi ich parami, a przez to również pomiędzy ti a tj.
        </p>
        <br>
        <br>
        <font size=3><b style=COLOR:#3d85c6>Rozgłaszanie przyczynowe - przykłady</b></font><br>
        <hr size=2><br>
      </div>
      <div id=il1v style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2312g24388f9_b.png" style=HEIGHT:342px;WIDTH:500px><br>
        <br>
        Na rysunku a) pokazano przykład dostarczenia przez proces <i>p</i> dwóch wiadomości, <i>m</i> i <i>m</i> <i>’.</i> Ponieważ wysłanie wiadomości <i>m</i> <i>’</i> następuje w procesie <i>r</i> po zdarzeniu odebrania wiadomości <i>m</i> , więc zgodnie definicją porządku przyczynowego (warunek 1) wiadomość <i>m</i> <i>’</i> jest przyczynowo zależna od <i>m</i> i jako taka powinna być dostarczona w każdym procesie <i>później</i> niż wiadomość <i>m</i> . Proces <i>p</i> właśnie tak dostarcza wiadomości <i>m</i> i <i>m</i> <i>’,</i> dzięki czemu porządek przyczynowy zostaje zachowany.<br>
        <br>
        <p>
          Na rysunku b) zaś widać przykład złamania porządku przyczynowego. Wiadomość <i>m</i> <i>’</i> zależna przyczynowo od <i>m</i> została dostarczona w procesie <i>p</i> <i>przed</i> wiadomością <i>m</i>&nbsp;; porządek przyczynowy został tutaj złamany.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          Ze względu na to, że własność uporządkowania przyczynowego jest ściśle silniejsza niż własność uporządkowania FIFO, zachowanie porządku przyczynowego implikuje zachowanie porządku FIFO.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          O wiadomościach, pomiędzy którymi nie zachodzi zależność przyczynowa mówi się, że są <i>przyczynowo</i> <i>niezależne</i> . Wiadomości przyczynowo niezależne mogą być dostarczone w dowolnej kolejności, a co za tym idzie – różne procesy mogą dostarczyć dwie (lub więcej) niezależne przyczynowo wiadomości w różnej kolejności. Wykonanie przykładu ilustrującego to pozostawia się Studentowi jako ćwiczenie.
        </p>
        <br>
        <br>
        <font size=3><b style=COLOR:#3d85c6>Algorytm Przyczynowy-RB</b></font><br>
        <hr size=2><br>
      </div>
      <div id=z0hl style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2313gfsc7hdz_b.png" style=HEIGHT:343px;WIDTH:500px><br>
        <br>
        Algorytm Przyczynowy-RB realizuje niezawodne rozgłoszenie z zachowaniem dodatkowo przyczynowego uporządkowania wiadomości. Algorytm opiera się na algorytmie FIFO-RB.<br>
        <br>
        <p>
          Główna idea algorytmu polega na rozsyłaniu danej wiadomości wraz <i>z</i> <i>całą</i> <i>sekwencją</i> <i>wiadomości</i> <i>ją</i> <i>poprzedzających</i> , czyli wiadomości, które proces nadawcy dostarczył przed rozesłaniem swojej. Ponieważ sekwencja jest uporządkowana, kolejność wiadomości w niej odzwierciedla porządek przyczynowy.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          W momencie dostarczenia danej wiadomości proces dołącza ją do sekwencji <i>poprzednie</i> . Następnie wykorzystuje tę sekwencję, gdy sam rozgłasza swoją wiadomość. Sekwencja ta niesie wówczas informację o wiadomościach, które proces nadawcy odebrał przed rozesłaniem własnej, a więc o wiadomościach poprzedzających przyczynowo rozsyłaną właśnie wiadomość. Sekwencja może zostać wyzerowana po rozgłoszeniu dowolnego komunikatu, ponieważ rozgłoszenie spowoduje przekazanie do wszystkich innych procesów informacji o uporządkowaniu komunikatów zaobserwowanym lokalnie.
        </p>
        <p>
          <br>
        </p>
        <p>
          /*sekwencja wiadomości, które <i>p</i> C-dostarczył od momentu swojego ostatniego C-rozgłoszenia*/
        </p>
        <br>
        <br>
        <font size=3><b style=COLOR:#3d85c6>Całkowite uporządkowanie</b></font><br>
        <hr size=2><br>
        <div id=v1ee style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2314cfxwm4g6_b.png" style=HEIGHT:344px;WIDTH:500px><br>
          <br>
          Własność <b>całkowitego</b> <b>uporządkowania</b> oznacza, że wszystkie wiadomości są dostarczane do wszystkich procesów w identycznej kolejności. Algorytm niezawodnego rozgłoszenia RB, który dodatkowo zachowuje całkowite uporządkowanie wiadomości, nazywamy niezawodnym rozgłoszeniem atomowym, w skrócie rozgłoszeniem atomowym RB lub ARB, od angielskiej nazwy Atomic Reliable Broadcast.<br>
          <br>
          <br>
          <font size=3><b style=COLOR:#3d85c6>Algorytmy czasowe</b></font><br>
          <hr size=2><br>
          <div id=byf5 style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2315gwwtx2gg_b.png" style=HEIGHT:343px;WIDTH:500px><br>
            <br>
            Algorytmy czasowe umożliwiają porządkowanie wiadomości w czasie rzeczywistym. Oparte są na założeniach o istnieniu maksymalnego, nieprzekraczalnego opóźnienia przy przesyłaniu wiadomości w systemie komunikacyjnym. Wyróżnia się dwa poziomy gwarancji algorytmów czasowych:<br>
            <br>
            <p>
              <b>Uporządkowanie</b> (ang. <i>Timeliness</i> ) <b>w</b> <b>czasie</b> <b>rzeczywistym</b> porządkuje wiadomości <i>względem</i> <i>momentu</i> <i>ich</i> <i>wysłania</i> <i>mierzonego</i> <i>w</i> <i>czasie</i> <i>rzeczywistym</i> , a więc bezwzględnym. Zrealizowanie go jest jednak możliwe tylko wtedy, gdy w systemie istnieje globalny zegar czasu rzeczywistego.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              <b>Uporządkowanie</b> <b>w</b> <b>czasie</b> <b>lokalnym</b> porządkuje wiadomości względem <i>lokalnego</i> <i>zegara</i> <i>u</i> <i>nadawcy</i> . Każdej rozsyłanej wiadomości przypisywany jest przez nadawcę tzw. „stempel czasowy” (ang. <i>Timestamp</i> ), oznaczony na slajdzie przez <i>ts(m</i> ).
            </p>
            <br>
            <br>
            <font size=3><b style=COLOR:#3d85c6>Algorytm Czasowy-RB</b></font><br>
            <hr size=2><br>
            <div id=fjq6 style=TEXT-ALIGN:left>
              <img src="images/dcjpvv6n_2316t5zf4jgn_b.png" style=HEIGHT:343px;WIDTH:500px><br>
              <br>
              Powyższy algorytm będzie w definicji algorytmów oznaczany przez R?. Oparte na nim algorytmy gwarantujące dodatkowo własności uporządkowania FIFO oraz przyczynowego, będą oznaczane kolejno przez F? i C?.<br>
              <br>
              <p>
                Załóżmy, że podsieć komunikacyjna ma następujące właściwości:<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                1. Co najwyżej <i>f</i> procesów może ulec awarii.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                2. Każde dwa poprawne procesy są połączone ścieżką długości co najwyżej <i>d</i> , złożonej wyłącznie z poprawnych
              </p>
              <p>
                procesów i łączy komunikacyjnych.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                3. Maksymalne opóźnienie wiadomości jest ograniczone stałą <i>?</i>.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                4. Czas wykonania lokalnej operacji jest zerowy.
              </p>
              <p>
                <br>
              </p>
              <p>
                Można udowodnić następujące <b>twierdzenie</b>&nbsp;:
              </p>
              <p>
                Przy założeniach 1-4, algorytm niezawodnego rozesłania RB zachowuje ?-<i>uporządkowanie</i> (<i>w</i> <i>czasie</i> <i>rzeczywistym</i> ) ze stałą <i>?</i> <i>=(</i> <i>f+d</i> <i>)</i> <i>?</i>.
              </p>
              <br>
              <br>
              <font size=3><b style=COLOR:#3d85c6>Algorytm Czasowy-Atomowy-RB</b></font><br>
              <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-3-wyk-2.0-Slajd34 title=Sr-3-wyk-2.0-Slajd34> </a><br>
              <div id=zb01 style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2317ggsdcvcv_b.png" style=HEIGHT:343px;WIDTH:500px><br>
                <br>
                W powyższym algorytmie wiadomość jest dostarczana w chwili <i>ts(m</i> )+?, czyli w chwili o ? późniejszej od wartości stempla czasowego wiadomości.<br>
                <br>
                <p>
                  Algorytm zachowuje całkowite uporządkowanie wiadomości, ponieważ można uszeregować liniowo stemple czasowe wszystkich otrzymywanych wiadomości i w każdym procesie uszeregowanie to będzie jednakowe. Dodanie do stempli czasowych stałej ? pozostawi to uszeregowanie bez zmian.<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  Algorytm nie gwarantuje jednak zachowania uporządkowania przyczynowego. Wykonanie przykładu ilustrującego ten fakt jest pozostawione Studentowi jako ćwiczenie.
                </p>
                <br>
                <br>
                <font size=3><b style=COLOR:#3d85c6>Algorytm Czasowy-Atomowy-</b><b style=COLOR:#3d85c6>Przyczynowy</b></font><br>
                <hr size=2><br>
                <div id=cfq6 style=TEXT-ALIGN:left>
                  <img src="images/dcjpvv6n_2321fmvbhkcc_b.png" style=HEIGHT:342px;WIDTH:500px>
                </div>
                <br>
                Powyższy algorytm zachowuje całkowite uporządkowanie wiadomości i jednocześnie uporządkowanie przyczynowe. Opiera się na działającym poniżej czasowym algorytmie przyczynowym-RB, gwarantującym uporządkowanie przyczynowe i dodatkowe gwarancje czasowe, i dodaje własność uporządkowania całkowitego. Skrót „CA” w nazwie algorytmu pochodzi od pełnej angielskiej nazwy <i>Causal</i> <i>Atomic</i> , oznaczającej „przyczynowy-atomowy”.<br>
                <br>
                <p>
                  Należy zauważyć, że algorytm bazowy, czasowy przyczynowy-RB, jest po prostu algorytmem przyczynowym przedstawionym wcześniej, lecz bazującym na czasowym algorytmie RB.
                </p>
                <br>
                <br>
                <font size=3><b style=COLOR:#3d85c6>Relacje pomiędzy algorytmami</b></font><br>
                <hr size=2><br>
              </div>
              <div id=v_v7 style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_23223dv6wbgs_b.png" style=HEIGHT:343px;WIDTH:500px><br>
                <br>
                <p>
                  Rysunek ukazuje, jak można w sposób warstwowy konstruować algorytmy dostarczające coraz bardziej wymagających gwarancji.<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  Podstawowy mechanizm rozgłoszenia niezawodnego może zostać wykorzystany jako podstawa dla wszystkich pozostałych. Algorytm z dodatkową własnością uporządkowania FIFO może z kolei posłużyć jako podstawa do implementacji algorytmu z uporządkowaniem przyczynowym. Ponadto, z prawej strony pokazano, że niezależnie od tych dwóch własności dany algorytm może zostać wyposażony w gwarancję całkowitego uporządkowania.
                </p>
                <br>
                <br>
                <font size=3><b style=COLOR:#3d85c6>Literatura</b></font><br>
                <hr size=2><br>
              </div>
              <div id=s11r style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2323g7p2z8d9_b.png" style=HEIGHT:341px;WIDTH:500px>
              </div>
              <br>
            </div>
          </div>
        </div>
      </div>
    </div>
  </div>
</div>
<br></body>
</html>